SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Matrix completion</title>

</head>

Matrix completion

</h1>

</header>

Matrix completion is the task of filling in the missing entries of a partially observed matrix, which is equivalent to performing data <a href="Imputation_(statistics)" title="Imputation (statistics)">imputation</a> in statistics. A wide range of datasets are naturally organized in matrix form. One example is the movie-ratings matrix, as appears in the <a href="Netflix_Prize" title="Netflix Prize">Netflix problem</a>: Given a ratings matrix in which each entry <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i,j)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i,j)}</annotation>

</semantics>

</math><img src="./8ef21910f980c6fca2b15bee102a7a0d861ed712.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.604ex; height:2.843ex;" alt="{\displaystyle (i,j)}" loading="lazy"> represents the rating of movie <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> by customer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">, if customer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> has watched movie <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> and is otherwise missing, we would like to predict the remaining entries in order to make good recommendations to customers on what to watch next. Another example is the <a href="Document-term_matrix" title="Document-term matrix">document-term matrix</a>: The frequencies of words used in a collection of documents can be represented as a matrix, where each entry corresponds to the number of times the associated term appears in the indicated document.

Without any restrictions on the number of <a href="Degrees_of_freedom" title="Degrees of freedom">degrees of freedom</a> in the completed matrix, this problem is <a href="Underdetermined_system" title="Underdetermined system">underdetermined</a> since the hidden entries could be assigned arbitrary values. Thus, we require some assumption on the matrix to create a <a href="Well-posed_problem" title="Well-posed problem">well-posed problem</a>, such as assuming it has maximal determinant, is positive definite, or is low-rank.<a href="#cite_note-johnson-1">[1]</a><a href="#cite_note-laurent-2">[2]</a>

For example, one may assume the matrix has low-rank structure, and then seek to find the lowest <a href="Rank_(linear_algebra)" title="Rank (linear algebra)">rank</a> matrix or, if the rank of the completed matrix is known, a matrix of <a href="Rank_(linear_algebra)" title="Rank (linear algebra)">rank</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> that matches the known entries. The illustration shows that a partially revealed rank-1 matrix (on the left) can be completed with zero-error (on the right) since all the rows with missing entries should be the same as the third row. In the case of the Netflix problem the ratings matrix is expected to be low-rank since user preferences can often be described by a few factors, such as the movie genre and time of release. Other applications include computer vision, where missing pixels in images need to be reconstructed, detecting the global positioning of sensors in a network from partial distance information, and <a href="Multiclass_classification" title="Multiclass classification">multiclass learning</a>. The matrix completion problem is in general <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a>, but under additional assumptions there are efficient algorithms that achieve exact reconstruction with high probability.

In statistical learning point of view, the matrix completion problem is an application of <a href="Matrix_regularization" title="Matrix regularization">matrix regularization</a> which is a generalization of vector <a href="Regularization_(mathematics)" title="Regularization (mathematics)">regularization</a>. For example, in the low-rank matrix completion problem one may apply the regularization penalty taking the form of a nuclear norm <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R(X)=\lambda \|X\|_{*}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R(X)=\lambda \|X\|_{*}}</annotation>

</semantics>

</math><img src="./fc90f159cac87095fb52f149e1333b268350480a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.366ex; height:2.843ex;" alt="{\displaystyle R(X)=\lambda \|X\|_{*}}" loading="lazy">

<div class="mw-heading mw-heading2"><h2 id="Low_rank_matrix_completion">Low rank matrix completion</h2></div>

One of the variants of the matrix completion problem is to find the lowest <a href="Rank_(linear_algebra)" title="Rank (linear algebra)">rank</a> matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> which matches the matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, which we wish to recover, for all entries in the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> of observed entries. The mathematical formulation of this problem is as follows:

<mtr>

<mtd>

</munder>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&{\text{rank}}(X)\\&{\text{subject to}}&X_{ij}=M_{ij}&\;\;\forall i,j\in E\\\end{aligned}}}</annotation>

</semantics>

</math><img src="./d3c448ed51f60d3363e50d7dd3f074c5be8e1d31.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:35.452ex; height:7.509ex;" alt="{\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&{\text{rank}}(X)\\&{\text{subject to}}&X_{ij}=M_{ij}&\;\;\forall i,j\in E\\\end{aligned}}}" loading="lazy"></dd></dl>

Candès and Recht<a href="#cite_note-candesrecht-3">[3]</a> proved that with assumptions on the sampling of the observed entries and sufficiently many sampled entries this problem has a unique solution with high probability.

An equivalent formulation, given that the matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> to be recovered is known to be of <a href="Rank_(linear_algebra)" title="Rank (linear algebra)">rank</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy">, is to solve for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{ij}=M_{ij}\;\;\forall i,j\in E}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{ij}=M_{ij}\;\;\forall i,j\in E}</annotation>

</semantics>

</math><img src="./4013ca57be7084d8cd154a41561703c28f380991.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:20.225ex; height:2.843ex;" alt="{\displaystyle X_{ij}=M_{ij}\;\;\forall i,j\in E}" loading="lazy">

<div class="mw-heading mw-heading3"><h3 id="Assumptions">Assumptions</h3></div>

A number of assumptions on the sampling of the observed entries and the number of sampled entries are frequently made to simplify the analysis and to ensure the problem is not <a href="Underdetermined_system" title="Underdetermined system">underdetermined</a>.

<div class="mw-heading mw-heading4"><h4 id="Uniform_sampling_of_observed_entries">Uniform sampling of observed entries</h4></div>

To make the analysis tractable, it is often assumed that the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> of observed entries and fixed <a href="Cardinality" title="Cardinality">cardinality</a> is sampled uniformly at random from the collection of all subsets of entries of cardinality <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |E|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |E|}</annotation>

</semantics>

</math><img src="./d8c2b9637808cf805d411190b4ae017dbd4ef8d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.069ex; height:2.843ex;" alt="{\displaystyle |E|}" loading="lazy">. To further simplify the analysis, it is instead assumed that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> is constructed by <a href="Bernoulli_sampling" title="Bernoulli sampling">Bernoulli sampling</a>, i.e. that each entry is observed with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy">. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> is set to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {N}{mn}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {N}{mn}}}</annotation>

</semantics>

</math><img src="./1d09dc59400c230968171f668ff84e3f41b5a8a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:4.271ex; height:5.176ex;" alt="{\displaystyle {\frac {N}{mn}}}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> is the desired expected <a href="Cardinality" title="Cardinality">cardinality</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m,\;n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m,\;n}</annotation>

</semantics>

</math><img src="./29073ac9f4f8730e0f05e38a656169b30b6e5a4a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.114ex; height:2.009ex;" alt="{\displaystyle m,\;n}" loading="lazy"> are the dimensions of the matrix (let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m<n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m<n}</annotation>

</semantics>

</math><img src="./490c01b0cb770144f28afd17bb5fef277daf6f38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.534ex; height:1.843ex;" alt="{\displaystyle m<n}" loading="lazy"> without loss of generality), <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |E|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |E|}</annotation>

</semantics>

</math><img src="./d8c2b9637808cf805d411190b4ae017dbd4ef8d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.069ex; height:2.843ex;" alt="{\displaystyle |E|}" loading="lazy"> is within <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> with high probability, thus <a href="Bernoulli_sampling" title="Bernoulli sampling">Bernoulli sampling</a> is a good approximation for uniform sampling.<a href="#cite_note-candesrecht-3">[3]</a> Another simplification is to assume that entries are sampled independently and with replacement.<a href="#cite_note-recht-4">[4]</a>

<div class="mw-heading mw-heading4"><h4 id="Lower_bound_on_number_of_observed_entries">Lower bound on number of observed entries</h4></div>

Suppose the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> (with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m<n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m<n}</annotation>

</semantics>

</math><img src="./490c01b0cb770144f28afd17bb5fef277daf6f38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.534ex; height:1.843ex;" alt="{\displaystyle m<n}" loading="lazy">) we are trying to recover has <a href="Rank_(linear_algebra)" title="Rank (linear algebra)">rank</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy">. There is an information theoretic lower bound on how many entries must be observed before <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> can be uniquely reconstructed. The set of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> matrices with rank less than or equal to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> is an algebraic variety in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathbb {C} }^{m\times n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathbb {C} }^{m\times n}}</annotation>

</semantics>

</math><img src="./60b79b87c0cf6b7acb09eac1de0dd58fc86a25cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.618ex; height:2.343ex;" alt="{\displaystyle {\mathbb {C} }^{m\times n}}" loading="lazy">with dimension <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n+m)r-r^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n+m)r-r^{2}}</annotation>

</semantics>

</math><img src="./6e8aeb46403ce10516191735bf91555b856f83b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.077ex; height:3.176ex;" alt="{\displaystyle (n+m)r-r^{2}}" loading="lazy">.

Using this result,

one can show that at least

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4nr-4r^{2}}</annotation>

</semantics>

</math><img src="./717de2f79ed230a1bd74c1db152ec08f5f673005.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.712ex; height:2.843ex;" alt="{\displaystyle 4nr-4r^{2}}" loading="lazy">

entries must be observed for matrix completion in

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathbb {C} }^{n\times n}}</annotation>

</semantics>

</math><img src="./095810ad6d10d2b030a3d52cf14b4fad7d48867d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.161ex; height:2.343ex;" alt="{\displaystyle {\mathbb {C} }^{n\times n}}" loading="lazy">

to have a unique solution

when

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\leq n/2}</annotation>

</semantics>

</math><img src="./34d654f2279fddad77c327f272d8503495455486.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.867ex; height:2.843ex;" alt="{\displaystyle r\leq n/2}" loading="lazy">

.<a href="#cite_note-xu-5">[5]</a>

Secondly, there must be at least one observed entry per row and column of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">. The <a href="Singular_value_decomposition" title="Singular value decomposition">singular value decomposition</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> is given by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U\Sigma V^{\dagger }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U\Sigma V^{\dagger }}</annotation>

</semantics>

</math><img src="./ee39d17d9be1b47b623948e61ec5fa5e0e5b19a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.34ex; height:2.676ex;" alt="{\displaystyle U\Sigma V^{\dagger }}" loading="lazy">. If row <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> is unobserved, it is easy to see the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i^{\text{th}}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i^{\text{th}}}</annotation>

</semantics>

</math><img src="./76cc827ec109594f9da6862138d76775cd733866.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.588ex; height:2.676ex;" alt="{\displaystyle i^{\text{th}}}" loading="lazy"> right singular vector of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation>

</semantics>

</math><img src="./7dffe5726650f6daac54829972a94f38eb8ec127.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}" loading="lazy">, can be changed to some arbitrary value and still yield a matrix matching <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> over the set of observed entries. Similarly, if column <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> is unobserved, the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j^{\text{th}}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j^{\text{th}}}</annotation>

</semantics>

</math><img src="./1a8170c26debcb1b3326c93ce9527b34af28581b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:2.771ex; height:3.009ex;" alt="{\displaystyle j^{\text{th}}}" loading="lazy"> left singular vector of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u_{i}}</annotation>

</semantics>

</math><img src="./14f13cb025ff2e136dcbd2fc81ddf965b728e3d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle u_{i}}" loading="lazy"> can be arbitrary. If we assume Bernoulli sampling of the set of observed entries, the <a href="Coupon_collector's_problem" title="Coupon collector's problem">Coupon collector effect</a> implies that entries on the order of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation>

</semantics>

</math><img src="./9d2320768fb54880ca4356e61f60eb02a3f9d9f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" loading="lazy"> must be observed to ensure that there is an observation from each row and column with high probability.<a href="#cite_note-candestao-6">[6]</a>

Combining the necessary conditions and assuming that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\ll m,n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\ll m,n}</annotation>

</semantics>

</math><img src="./c837eb99f4ec91dba6ee34903117d47a102230a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.132ex; height:2.176ex;" alt="{\displaystyle r\ll m,n}" loading="lazy"> (a valid assumption for many practical applications), the lower bound on the number of observed entries required to prevent the problem of matrix completion from being underdetermined is on the order of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle nr\log n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle nr\log n}</annotation>

</semantics>

</math><img src="./50bb5d0e2c4e47f45a0e62183ed4841f300c95fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.584ex; height:2.509ex;" alt="{\displaystyle nr\log n}" loading="lazy">.

<div class="mw-heading mw-heading4"><h4 id="Incoherence">Incoherence</h4></div>

The concept of incoherence arose in <a href="Compressed_sensing" title="Compressed sensing">compressed sensing</a>. It is introduced in the context of matrix completion to ensure the singular vectors of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> are not too "sparse" in the sense that all coordinates of each singular vector are of comparable magnitude instead of just a few coordinates having significantly larger magnitudes.<a href="#cite_note-tao-7">[7]</a><a href="#cite_note-nguyenkimshim-8">[8]</a> The standard basis vectors are then undesirable as singular vectors, and the vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{\sqrt {n}}}{\begin{bmatrix}1\\1\\\vdots \\1\end{bmatrix}}}">

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{\sqrt {n}}}{\begin{bmatrix}1\\1\\\vdots \\1\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./7b897494d726877f5f30a131e03b4f6ef94119a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.338ex; width:9.181ex; height:13.843ex;" alt="{\displaystyle {\frac {1}{\sqrt {n}}}{\begin{bmatrix}1\\1\\\vdots \\1\end{bmatrix}}}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{n}}</annotation>

</semantics>

</math><img src="./c510b63578322050121fe966f2e5770bea43308d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.897ex; height:2.343ex;" alt="{\displaystyle \mathbb {R} ^{n}}" loading="lazy"> is desirable. As an example of what could go wrong if the singular vectors are sufficiently "sparse", consider the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}}">

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./e4189bbebd9e5005b4080b962db28c3e93b7f8ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.671ex; width:17.03ex; height:10.509ex;" alt="{\displaystyle {\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}}" loading="lazy"> with <a href="Singular_value_decomposition" title="Singular value decomposition">singular value decomposition</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I_{m}{\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}I_{n}}">

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{m}{\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}I_{n}}</annotation>

</semantics>

</math><img src="./189f198e43636e2461614d312009bc1bbc0723bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.671ex; width:21.97ex; height:10.509ex;" alt="{\displaystyle I_{m}{\begin{bmatrix}1&0&\cdots &0\\\vdots &&\vdots \\0&0&0&0\end{bmatrix}}I_{n}}" loading="lazy">. Almost all the entries of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> must be sampled before it can be reconstructed.

Candès and Recht<a href="#cite_note-candesrecht-3">[3]</a> define the coherence of a matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> with <a href="Column_space" class="mw-redirect" title="Column space">column space</a> an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r-}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r-}</annotation>

</semantics>

</math><img src="./1d1ac3706a3c6b53a6794c2dc17dc57319199f15.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.857ex; height:2.176ex;" alt="{\displaystyle r-}" loading="lazy">dimensional subspace of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{n}}</annotation>

</semantics>

</math><img src="./c510b63578322050121fe966f2e5770bea43308d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.897ex; height:2.343ex;" alt="{\displaystyle \mathbb {R} ^{n}}" loading="lazy"> as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu (U)={\frac {n}{r}}\max _{i<n}\|P_{U}e_{i}\|^{2}}">

<mfrac>

</mfrac>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu (U)={\frac {n}{r}}\max _{i<n}\|P_{U}e_{i}\|^{2}}</annotation>

</semantics>

</math><img src="./230b55409a2fe493a259d01a9bbc7f6068250d78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:23.67ex; height:4.843ex;" alt="{\displaystyle \mu (U)={\frac {n}{r}}\max _{i<n}\|P_{U}e_{i}\|^{2}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{U}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{U}}</annotation>

</semantics>

</math><img src="./8a68b9b0fa53a09fa18dc4c16b16b4153b6c4047.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.985ex; height:2.509ex;" alt="{\displaystyle P_{U}}" loading="lazy"> is the orthogonal <a href="Projection_(mathematics)" title="Projection (mathematics)">projection</a> onto <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy">. Incoherence then asserts that given the <a href="Singular_value_decomposition" title="Singular value decomposition">singular value decomposition</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U\Sigma V^{\dagger }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U\Sigma V^{\dagger }}</annotation>

</semantics>

</math><img src="./ee39d17d9be1b47b623948e61ec5fa5e0e5b19a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.34ex; height:2.676ex;" alt="{\displaystyle U\Sigma V^{\dagger }}" loading="lazy"> of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">,

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu (U),\;\mu (V)\leq \mu _{0}}</annotation>

</semantics>

</math><img src="./16bfa31c359786e9c77186c963bff036c475e348.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.225ex; height:2.843ex;" alt="{\displaystyle \mu (U),\;\mu (V)\leq \mu _{0}}" loading="lazy"></li>

<li>The entries of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{k}u_{k}v_{k}^{\dagger }}">

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{k}u_{k}v_{k}^{\dagger }}</annotation>

</semantics>

</math><img src="./025a192492f49aec3ef1f4651e50c69ebd6ae69d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:8.377ex; height:5.509ex;" alt="{\displaystyle \sum _{k}u_{k}v_{k}^{\dagger }}" loading="lazy"> have magnitudes upper bounded by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{1}{\sqrt {\frac {r}{mn}}}}">

<msub>

</mrow>

</msub>

<msqrt>

<mfrac>

<mrow>

</mrow>

</mfrac>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{1}{\sqrt {\frac {r}{mn}}}}</annotation>

</semantics>

</math><img src="./0353e80af56ef839781eba3e12bb683c6d6e8a84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:9.051ex; height:6.343ex;" alt="{\displaystyle \mu _{1}{\sqrt {\frac {r}{mn}}}}" loading="lazy"></li></ol>

for some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{0},\;\mu _{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{0},\;\mu _{1}}</annotation>

</semantics>

</math><img src="./dfacdacbe5f00af99c023eadf6233d5d7dfe0e08.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.591ex; height:2.176ex;" alt="{\displaystyle \mu _{0},\;\mu _{1}}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Low_rank_matrix_completion_with_noise">Low rank matrix completion with noise</h2></div>

In real world application, one often observe only a few entries corrupted at least by a small amount of noise. For example, in the Netflix problem, the ratings are uncertain. Candès and Plan<a href="#cite_note-candesplan-9">[9]</a> showed that it is possible to fill in the many missing entries of large low-rank matrices from just a few noisy samples by nuclear norm minimization. The noisy model assumes that we observe

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y_{ij}=M_{ij}+Z_{ij},(i,j)\in \Omega ,}</annotation>

</semantics>

</math><img src="./484e3a51d91b33f7db2d4b500ce66197c559a33d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:26.366ex; height:3.009ex;" alt="{\displaystyle Y_{ij}=M_{ij}+Z_{ij},(i,j)\in \Omega ,}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {Z_{ij}:(i,j)\in \Omega }}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {Z_{ij}:(i,j)\in \Omega }}</annotation>

</semantics>

</math><img src="./eea0037af1cdd41b43966ea4eb5d97d451ff7a85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:14.124ex; height:3.009ex;" alt="{\displaystyle {Z_{ij}:(i,j)\in \Omega }}" loading="lazy"> is a noise term. Note that the noise can be either stochastic or deterministic. Alternatively the model can be expressed as

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{\Omega }(Y)=P_{\Omega }(M)+P_{\Omega }(Z),}</annotation>

</semantics>

</math><img src="./c008a6dd2d988367d026b6aa7b323260be1251f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.643ex; height:2.843ex;" alt="{\displaystyle P_{\Omega }(Y)=P_{\Omega }(M)+P_{\Omega }(Z),}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Z}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z}</annotation>

</semantics>

</math><img src="./1cc6b75e09a8aa3f04d8584b11db534f88fb56bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.68ex; height:2.176ex;" alt="{\displaystyle Z}" loading="lazy"> is an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\times n}</annotation>

</semantics>

</math><img src="./59d2b4cb72e304526cf5b5887147729ea259da78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.63ex; height:1.676ex;" alt="{\displaystyle n\times n}" loading="lazy"> matrix with entries <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Z_{ij}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z_{ij}}</annotation>

</semantics>

</math><img src="./6b9903985b6f9d7991e5439eb3932a5cc4aed27e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.065ex; height:2.843ex;" alt="{\displaystyle Z_{ij}}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i,j)\in \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i,j)\in \Omega }</annotation>

</semantics>

</math><img src="./4737104070acee6a5d656df6b3d78d432b8cde78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.122ex; height:2.843ex;" alt="{\displaystyle (i,j)\in \Omega }" loading="lazy"> assuming that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|P_{\Omega }(Z)\|_{F}\leq \delta }">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|P_{\Omega }(Z)\|_{F}\leq \delta }</annotation>

</semantics>

</math><img src="./85aaeada36d6a4be44941e3af024080991b36ac1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.336ex; height:2.843ex;" alt="{\displaystyle \|P_{\Omega }(Z)\|_{F}\leq \delta }" loading="lazy"> for some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta >0}</annotation>

</semantics>

</math><img src="./595d5cea06fdcaf2642caf549eda2cfc537958a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.31ex; height:2.343ex;" alt="{\displaystyle \delta >0}" loading="lazy"> .To recover the incomplete matrix, we try to solve the following optimization problem:

<mtr>

<mtd>

</munder>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&\|X\|_{*}\\&{\text{subject to}}&\|P_{\Omega }(X-Y)\|_{F}\leq \delta \\\end{aligned}}}</annotation>

</semantics>

</math><img src="./7183da0eb025dc38ac9eddde4b1e849865056026.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:34.476ex; height:7.176ex;" alt="{\displaystyle {\begin{aligned}&{\underset {X}{\text{min}}}&\|X\|_{*}\\&{\text{subject to}}&\|P_{\Omega }(X-Y)\|_{F}\leq \delta \\\end{aligned}}}" loading="lazy"></dd></dl>

Among all matrices consistent with the data, find the one with minimum nuclear norm. Candès and Plan<a href="#cite_note-candesplan-9">[9]</a> have shown that this reconstruction is accurate. They have proved that when perfect noiseless recovery occurs, then matrix completion is stable vis a vis perturbations. The error is proportional to the noise level <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>

</semantics>

</math><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy">. Therefore, when the noise level is small, the error is small. Here the matrix completion problem does not obey the restricted isometry property (RIP). For matrices, the RIP would assume that the sampling operator obeys

</mrow>

</mrow>

</msubsup>

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1-\delta )\|X\|_{F}^{2}\leq {\frac {1}{p}}\|P_{\Omega }(X)\|_{F}^{2}\leq (1+\delta )\|X\|_{F}^{2}}</annotation>

</semantics>

</math><img src="./b253165f59cb71ebed9c2cf6717df8e4eb76f629.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:43.949ex; height:5.676ex;" alt="{\displaystyle (1-\delta )\|X\|_{F}^{2}\leq {\frac {1}{p}}\|P_{\Omega }(X)\|_{F}^{2}\leq (1+\delta )\|X\|_{F}^{2}}" loading="lazy"></dd></dl>

for all matrices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> with sufficiently small rank and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta <1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta <1}</annotation>

</semantics>

</math><img src="./433aaf73dfe4bbc3efeaffce3c4700834d2dc035.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.31ex; height:2.343ex;" alt="{\displaystyle \delta <1}" loading="lazy"> sufficiently small.

The methods are also applicable to sparse signal recovery problems in which the RIP does not hold.

<div class="mw-heading mw-heading2"><h2 id="High-rank_matrix_completion">High-rank matrix completion</h2></div>

The high-rank matrix completion in general is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a>. However, with certain assumptions, some incomplete high rank matrix or even full rank matrix can be completed.

Eriksson, Balzano and Nowak<a href="#cite_note-erikssonbalzano-10">[10]</a> have considered the problem of completing a matrix with the assumption that the columns of the matrix belong to a union of multiple low-rank subspaces. Since the columns belong to a union of subspaces, the problem may be viewed as a missing-data version of the <a href="Clustering_high-dimensional_data" title="Clustering high-dimensional data">subspace clustering</a> problem. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> be an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\times N}</annotation>

</semantics>

</math><img src="./ee704f107aab7b2b5a97e0c1fb96dc159f9626f2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.299ex; height:2.176ex;" alt="{\displaystyle n\times N}" loading="lazy"> matrix whose (complete) columns lie in a union of at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> subspaces, each of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {rank} \leq r<n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {rank} \leq r<n}</annotation>

</semantics>

</math><img src="./3beb8d62393fb38068a2e9bbbdc862a067e6c15e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.234ex; height:2.343ex;" alt="{\displaystyle \operatorname {rank} \leq r<n}" loading="lazy">, and assume <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\gg kn}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\gg kn}</annotation>

</semantics>

</math><img src="./edbffd734d680c053c5b3204b79ae134d67c5db3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.284ex; height:2.176ex;" alt="{\displaystyle N\gg kn}" loading="lazy">. Eriksson, Balzano and Nowak<a href="#cite_note-erikssonbalzano-10">[10]</a> showed that under mild assumptions each column of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> can be perfectly recovered with high probability from an incomplete version so long as at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle CrN\log ^{2}(n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle CrN\log ^{2}(n)}</annotation>

</semantics>

</math><img src="./879115fab5151b3f50aad657ce907f42c8ae336f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.496ex; height:3.176ex;" alt="{\displaystyle CrN\log ^{2}(n)}" loading="lazy"> entries of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> are observed uniformly at random, with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C>1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C>1}</annotation>

</semantics>

</math><img src="./536c544fc840b3b0bc20994827352e7396cf3e5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.027ex; height:2.176ex;" alt="{\displaystyle C>1}" loading="lazy"> a constant depending on the usual incoherence conditions, the geometrical arrangement of subspaces, and the distribution of columns over the subspaces.

The algorithm involves several steps: (1) local neighborhoods; (2) local subspaces; (3) subspace refinement; (4) full matrix completion. This method can be applied to Internet distance matrix completion and topology identification.

<div class="mw-heading mw-heading2"><h2 id="Algorithms_for_low-rank_matrix_completion">Algorithms for low-rank matrix completion</h2></div>

Various matrix completion algorithms have been proposed.<a href="#cite_note-nguyenkimshim-8">[8]</a> These include convex relaxation-based algorithm,<a href="#cite_note-candesrecht-3">[3]</a> gradient-based algorithm,<a href="#cite_note-keshavan-11">[11]</a> alternating minimization-based algorithm,<a href="#cite_note-jainnetrapalli-12">[12]</a> Gauss-Newton algorithm,<a href="#cite_note-Zilber2022-13">[13]</a> and discrete-aware based algorithm.<a href="#cite_note-Fuhrling2023-14">[14]</a>

<div class="mw-heading mw-heading3"><h3 id="Convex_relaxation">Convex relaxation</h3></div>

The rank minimization problem is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a>. One approach, proposed by Candès and Recht, is to form a <a href="Convex_function" title="Convex function">convex</a> relaxation of the problem and minimize the nuclear <a href="Norm_(mathematics)" title="Norm (mathematics)">norm</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|M\|_{*}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|M\|_{*}}</annotation>

</semantics>

</math><img src="./45eca8951411833ce9a30dc39338808206f4d575.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.821ex; height:2.843ex;" alt="{\displaystyle \|M\|_{*}}" loading="lazy"> (which gives the sum of the <a href="Singular_value" title="Singular value">singular values</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">) instead of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{rank}}(M)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{rank}}(M)}</annotation>

</semantics>

</math><img src="./2aabff4b0aef1342fe453ce373019709cf5d1b25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.846ex; height:2.843ex;" alt="{\displaystyle {\text{rank}}(M)}" loading="lazy"> (which counts the number of non zero <a href="Singular_value" title="Singular value">singular values</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">).<a href="#cite_note-candesrecht-3">[3]</a> This is analogous to minimizing the L1-<a href="Norm_(mathematics)" title="Norm (mathematics)">norm</a> rather than the L0-<a href="Norm_(mathematics)" title="Norm (mathematics)">norm</a> for vectors. The <a href="Convex_function" title="Convex function">convex</a> relaxation can be solved using <a href="Semidefinite_programming" title="Semidefinite programming">semidefinite programming</a> (SDP) by noticing that the optimization problem is equivalent to

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mtd>

<mtd>

<mi>trace</mi>

<msub>

</mrow>

</msub>

<mi>trace</mi>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&\min \limits _{W_{1},W_{2}}&&\operatorname {trace} (W_{1})+\operatorname {trace} (W_{2})\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\begin{bmatrix}W_{1}&X\\X^{T}&W_{2}\end{bmatrix}}\succeq 0\end{aligned}}}</annotation>

</semantics>

</math><img src="./8ccca7119f881c1338aefda6c91439cb38a2d81b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.505ex; width:38.269ex; height:14.176ex;" alt="{\displaystyle {\begin{aligned}&\min \limits _{W_{1},W_{2}}&&\operatorname {trace} (W_{1})+\operatorname {trace} (W_{2})\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&{\begin{bmatrix}W_{1}&X\\X^{T}&W_{2}\end{bmatrix}}\succeq 0\end{aligned}}}" loading="lazy"></dd></dl>

The complexity of using <a href="Semidefinite_programming" title="Semidefinite programming">SDP</a> to solve the convex relaxation is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\text{max}}(m,n)^{4})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\text{max}}(m,n)^{4})}</annotation>

</semantics>

</math><img src="./f9049c4d03664b1d223e849d40c163327e66b028.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.241ex; height:3.176ex;" alt="{\displaystyle O({\text{max}}(m,n)^{4})}" loading="lazy">. State of the art solvers like SDPT3 can only handle matrices of size up to 100 by 100.<a href="#cite_note-caicandesshen-15">[15]</a> An alternative first order method that approximately solves the convex relaxation is the Singular Value Thresholding Algorithm introduced by Cai, Candès and Shen.<a href="#cite_note-caicandesshen-15">[15]</a>

Candès and Recht show, using the study of random variables on <a href="Banach_space" title="Banach space">Banach spaces</a>, that if the number of observed entries is on the order of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \max {\{\mu _{1}^{2},{\sqrt {\mu _{0}}}\mu _{1},\mu _{0}n^{0.25}\}}nr\log n}">

</mrow>

</mrow>

</msubsup>

<msqrt>

<msub>

</mrow>

</msub>

</msqrt>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max {\{\mu _{1}^{2},{\sqrt {\mu _{0}}}\mu _{1},\mu _{0}n^{0.25}\}}nr\log n}</annotation>

</semantics>

</math><img src="./7a16694353d876ee111e9fb39cdb954e1209ce8b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:33ex; height:3.509ex;" alt="{\displaystyle \max {\{\mu _{1}^{2},{\sqrt {\mu _{0}}}\mu _{1},\mu _{0}n^{0.25}\}}nr\log n}" loading="lazy"> (assume without loss of generality <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m<n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m<n}</annotation>

</semantics>

</math><img src="./490c01b0cb770144f28afd17bb5fef277daf6f38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.534ex; height:1.843ex;" alt="{\displaystyle m<n}" loading="lazy">), the rank minimization problem has a unique solution which also happens to be the solution of its convex relaxation with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-{\frac {c}{n^{3}}}}">

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-{\frac {c}{n^{3}}}}</annotation>

</semantics>

</math><img src="./c0b4341d47cec99e59c0ae573220e358aae8c140.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:7.288ex; height:5.009ex;" alt="{\displaystyle 1-{\frac {c}{n^{3}}}}" loading="lazy"> for some constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy">. If the rank of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> is small (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\leq {\frac {n^{0.2}}{\mu _{0}}}}">

<mfrac>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\leq {\frac {n^{0.2}}{\mu _{0}}}}</annotation>

</semantics>

</math><img src="./2cd458c219e0010774ad29db705593dad5a1bb28.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:8.712ex; height:6.176ex;" alt="{\displaystyle r\leq {\frac {n^{0.2}}{\mu _{0}}}}" loading="lazy">), the size of the set of observations reduces to the order of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{0}n^{1.2}r\log n}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{0}n^{1.2}r\log n}</annotation>

</semantics>

</math><img src="./89a2577d393968a2e2c86adbff91c65e0d3c517d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.374ex; height:3.176ex;" alt="{\displaystyle \mu _{0}n^{1.2}r\log n}" loading="lazy">. These results are near optimal, since the minimum number of entries that must be observed for the matrix completion problem to not be underdetermined is on the order of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle nr\log n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle nr\log n}</annotation>

</semantics>

</math><img src="./50bb5d0e2c4e47f45a0e62183ed4841f300c95fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.584ex; height:2.509ex;" alt="{\displaystyle nr\log n}" loading="lazy">.

This result has been improved by Candès and Tao.<a href="#cite_note-candestao-6">[6]</a> They achieve bounds that differ from the optimal bounds only by <a href="Polylogarithmic_function" title="Polylogarithmic function">polylogarithmic</a> factors by strengthening the assumptions. Instead of the incoherence property, they assume the strong incoherence property with parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{3}}</annotation>

</semantics>

</math><img src="./f144b856b549cd520d34b8b6834c55742af18acc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.456ex; height:2.176ex;" alt="{\displaystyle \mu _{3}}" loading="lazy">. This property states that:

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

<msup>

</msup>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

<msub>

<msup>

</msup>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\langle e_{a},P_{U}e_{a'}\rangle -{\frac {r}{m}}1_{a=a'}|\leq \mu _{3}{\frac {\sqrt {r}}{m}}}</annotation>

</semantics>

</math><img src="./d99d24fc2eaa30c47d9ef6bbfbde3934a2156c6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:32.06ex; height:5.843ex;" alt="{\displaystyle |\langle e_{a},P_{U}e_{a'}\rangle -{\frac {r}{m}}1_{a=a'}|\leq \mu _{3}{\frac {\sqrt {r}}{m}}}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a,a'\leq m}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a,a'\leq m}</annotation>

</semantics>

</math><img src="./211ef3f9a5a32d98aa80d7a8bcb36fcff8da9827.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.317ex; height:2.843ex;" alt="{\displaystyle a,a'\leq m}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\langle e_{b},P_{U}e_{b'}\rangle -{\frac {r}{n}}1_{b=b'}|\leq \mu _{3}{\frac {\sqrt {r}}{n}}}">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

<msup>

</msup>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

<msub>

<msup>

</msup>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\langle e_{b},P_{U}e_{b'}\rangle -{\frac {r}{n}}1_{b=b'}|\leq \mu _{3}{\frac {\sqrt {r}}{n}}}</annotation>

</semantics>

</math><img src="./10a5712db60c438443d7b7d273a5f2b22258364c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:30.758ex; height:5.843ex;" alt="{\displaystyle |\langle e_{b},P_{U}e_{b'}\rangle -{\frac {r}{n}}1_{b=b'}|\leq \mu _{3}{\frac {\sqrt {r}}{n}}}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b,b'\leq n}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b,b'\leq n}</annotation>

</semantics>

</math><img src="./12d59e79d08448e78f5d79964a374aa7d5c1e8f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.207ex; height:2.843ex;" alt="{\displaystyle b,b'\leq n}" loading="lazy"></li>

<li>The entries of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{i}u_{i}v_{i}^{\dagger }}">

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i}u_{i}v_{i}^{\dagger }}</annotation>

</semantics>

</math><img src="./6ac6076ad6d9149f7ab680e6f0c8757d05022095.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:7.961ex; height:5.509ex;" alt="{\displaystyle \sum _{i}u_{i}v_{i}^{\dagger }}" loading="lazy"> are bounded in magnitude by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{3}{\sqrt {\frac {r}{mn}}}}">

<msub>

</mrow>

</msub>

<msqrt>

<mfrac>

<mrow>

</mrow>

</mfrac>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{3}{\sqrt {\frac {r}{mn}}}}</annotation>

</semantics>

</math><img src="./7ed615b47baa6aa3df728769f2d5892064f13064.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:9.051ex; height:6.343ex;" alt="{\displaystyle \mu _{3}{\sqrt {\frac {r}{mn}}}}" loading="lazy"></li></ol>

Intuitively, strong incoherence of a matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> asserts that the orthogonal projections of standard basis vectors to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> has magnitudes that have high likelihood if the singular vectors were distributed randomly.<a href="#cite_note-tao-7">[7]</a>

Candès and Tao find that when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"> and the number of observed entries is on the order of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{3}^{4}n(\log n)^{2}}">

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{3}^{4}n(\log n)^{2}}</annotation>

</semantics>

</math><img src="./5729e7d9da54f2ac84953eba1f88e541220bb9c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.468ex; height:3.343ex;" alt="{\displaystyle \mu _{3}^{4}n(\log n)^{2}}" loading="lazy">, the rank minimization problem has a unique solution which also happens to be the solution of its convex relaxation with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-{\frac {c}{n^{3}}}}">

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-{\frac {c}{n^{3}}}}</annotation>

</semantics>

</math><img src="./c0b4341d47cec99e59c0ae573220e358aae8c140.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:7.288ex; height:5.009ex;" alt="{\displaystyle 1-{\frac {c}{n^{3}}}}" loading="lazy"> for some constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy">. For arbitrary <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy">, the number of observed entries sufficient for this assertion hold true is on the order of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{3}^{2}nr(\log n)^{6}}">

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{3}^{2}nr(\log n)^{6}}</annotation>

</semantics>

</math><img src="./3cb083d281c4b0e0f2e9b7c8f37a084838063fae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.516ex; height:3.343ex;" alt="{\displaystyle \mu _{3}^{2}nr(\log n)^{6}}" loading="lazy">

Another convex relaxation approach<a href="#cite_note-bertsimas2021mixed-16">[16]</a> is to minimize the Frobenius squared norm under a rank constraint. This is equivalent to solving

<mtr>

<mtd>

</mrow>

</munder>

</mtd>

<mtd>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&\min \limits _{X}&&\Vert X\Vert _{F}^{2}\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&\operatorname {Rank} (X)\leq k.\end{aligned}}}</annotation>

</semantics>

</math><img src="./4f0c29000edeb1259df138fc4aa4a9db4f73cede.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.671ex; width:35.452ex; height:10.509ex;" alt="{\displaystyle {\begin{aligned}&\min \limits _{X}&&\Vert X\Vert _{F}^{2}\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&\operatorname {Rank} (X)\leq k.\end{aligned}}}" loading="lazy"></dd></dl>

By introducing an orthogonal projection matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> (meaning <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y^{2}=Y,Y=Y'}">

<msup>

</mrow>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y^{2}=Y,Y=Y'}</annotation>

</semantics>

</math><img src="./e545b6ec4c4a033a434b315572f1f00b298beeba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.317ex; height:3.009ex;" alt="{\displaystyle Y^{2}=Y,Y=Y'}" loading="lazy">) to model the rank of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> via <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X=YX,{\text{trace}}(Y)\leq k}">

<mtext>trace</mtext>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X=YX,{\text{trace}}(Y)\leq k}</annotation>

</semantics>

</math><img src="./f69eb69eac5996f485632f512e952611a6c7181a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.802ex; height:2.843ex;" alt="{\displaystyle X=YX,{\text{trace}}(Y)\leq k}" loading="lazy"> and taking this problem's convex relaxation, we obtain the following semidefinite program

<mtr>

<mtd>

</mrow>

</munder>

</mtd>

<mtd>

<mtext>trace</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mi>trace</mi>

</mtd>

</mtr>

<mtr>

<mtd>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&\min \limits _{X,Y,\theta }&&{\text{trace}}(\theta )\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&\operatorname {trace} (Y)\leq k,0\preceq Y\preceq I\\&&&{\begin{pmatrix}Y&X\\X^{\top }&\theta \end{pmatrix}}\succeq 0.\end{aligned}}}</annotation>

</semantics>

</math><img src="./b3e36fef019548144c2bd0332c7236da5bddb3e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -8.005ex; width:39.501ex; height:17.176ex;" alt="{\displaystyle {\begin{aligned}&\min \limits _{X,Y,\theta }&&{\text{trace}}(\theta )\\&{\text{subject to}}&&X_{ij}=M_{ij}\;\;\forall i,j\in E\\&&&\operatorname {trace} (Y)\leq k,0\preceq Y\preceq I\\&&&{\begin{pmatrix}Y&X\\X^{\top }&\theta \end{pmatrix}}\succeq 0.\end{aligned}}}" loading="lazy"></dd></dl>

If Y is a projection matrix (i.e., has binary eigenvalues) in this relaxation, then the relaxation is tight. Otherwise, it gives a valid lower bound on the overall objective. Moreover, it can be converted into a feasible solution with a (slightly) larger objective by rounding the eigenvalues of Y greedily.<a href="#cite_note-bertsimas2021mixed-16">[16]</a> Remarkably, this convex relaxation can be solved by alternating minimization on X and Y without solving any SDPs, and thus it scales beyond the typical numerical limits of state-of-the-art SDP solvers like SDPT3 or Mosek.

This approach is a special case of a more general reformulation technique, which can be applied to obtain a valid lower bound on any low-rank problem with a trace-matrix-convex objective.<a href="#cite_note-bertsimas2021perspective-17">[17]</a>

<div class="mw-heading mw-heading3"><h3 id="Gradient_descent">Gradient descent</h3></div>

Keshavan, Montanari and Oh<a href="#cite_note-keshavan-11">[11]</a> consider a variant of matrix completion where the <a href="Rank_(linear_algebra)" title="Rank (linear algebra)">rank</a> of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, which is to be recovered, is known to be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy">. They assume <a href="Bernoulli_sampling" title="Bernoulli sampling">Bernoulli sampling</a> of entries, constant aspect ratio <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {m}{n}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {m}{n}}}</annotation>

</semantics>

</math><img src="./d48d87468620ad6c70385ddd0d024577ccb559e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:2.877ex; height:4.676ex;" alt="{\displaystyle {\frac {m}{n}}}" loading="lazy">, bounded magnitude of entries of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> (let the upper bound be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{\text{max}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{\text{max}}}</annotation>

</semantics>

</math><img src="./db024154a635456210f15cc22e0f8b16b601c70a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.545ex; height:2.509ex;" alt="{\displaystyle M_{\text{max}}}" loading="lazy">), and constant <a href="Condition_number" title="Condition number">condition number</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {\sigma _{1}}{\sigma _{r}}}}">

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {\sigma _{1}}{\sigma _{r}}}}</annotation>

</semantics>

</math><img src="./f957ab16da7ca87cd1eca844c806a5ae17baff18.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:3.218ex; height:5.009ex;" alt="{\displaystyle {\frac {\sigma _{1}}{\sigma _{r}}}}" loading="lazy"> (where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma _{1}}</annotation>

</semantics>

</math><img src="./7fa0e56273a1cb32709b442e2421e9f947522b84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.382ex; height:2.009ex;" alt="{\displaystyle \sigma _{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma _{r}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma _{r}}</annotation>

</semantics>

</math><img src="./58fb3ca75d72580c2e18828af80e6fc9f4d2d72a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.301ex; height:2.009ex;" alt="{\displaystyle \sigma _{r}}" loading="lazy"> are the largest and smallest <a href="Singular_value" title="Singular value">singular values</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> respectively). Further, they assume the two incoherence conditions are satisfied with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{0}}</annotation>

</semantics>

</math><img src="./fe2fd9b8decb38a3cd158e7b6c0c6e2d987fefcc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.456ex; height:2.176ex;" alt="{\displaystyle \mu _{0}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{1}{\frac {\sigma _{1}}{\sigma _{r}}}}">

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{1}{\frac {\sigma _{1}}{\sigma _{r}}}}</annotation>

</semantics>

</math><img src="./2d4d01a8ceb5d42ff5524243dd4edb353d020044.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:5.674ex; height:5.009ex;" alt="{\displaystyle \mu _{1}{\frac {\sigma _{1}}{\sigma _{r}}}}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{0}}</annotation>

</semantics>

</math><img src="./fe2fd9b8decb38a3cd158e7b6c0c6e2d987fefcc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.456ex; height:2.176ex;" alt="{\displaystyle \mu _{0}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{1}}</annotation>

</semantics>

</math><img src="./d6899621035d3359b9c1c064739b54c7004e220d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.456ex; height:2.176ex;" alt="{\displaystyle \mu _{1}}" loading="lazy"> are constants. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M^{E}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M^{E}}</annotation>

</semantics>

</math><img src="./96b567d2470154580c0d340c1d7dfe4847a425a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.987ex; height:2.676ex;" alt="{\displaystyle M^{E}}" loading="lazy"> be a matrix that matches <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> on the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> of observed entries and is 0 elsewhere. They then propose the following algorithm:

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M^{E}}</annotation>

</semantics>

</math><img src="./96b567d2470154580c0d340c1d7dfe4847a425a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.987ex; height:2.676ex;" alt="{\displaystyle M^{E}}" loading="lazy"> by removing all observations from columns with degree larger than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {2|E|}{n}}}">

<mfrac>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {2|E|}{n}}}</annotation>

</semantics>

</math><img src="./7648a6ddfae698be83b0de301c9341d7c8ee1d72.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:5.068ex; height:5.676ex;" alt="{\displaystyle {\frac {2|E|}{n}}}" loading="lazy"> by setting the entries in the columns to 0. Similarly remove all observations from rows with degree larger than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {2|E|}{n}}}">

<mfrac>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {2|E|}{n}}}</annotation>

</semantics>

</math><img src="./7648a6ddfae698be83b0de301c9341d7c8ee1d72.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:5.068ex; height:5.676ex;" alt="{\displaystyle {\frac {2|E|}{n}}}" loading="lazy">.</li>

<li>Project <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M^{E}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M^{E}}</annotation>

</semantics>

</math><img src="./96b567d2470154580c0d340c1d7dfe4847a425a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.987ex; height:2.676ex;" alt="{\displaystyle M^{E}}" loading="lazy"> onto its first <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> <a href="Principal_component_analysis" title="Principal component analysis">principal components</a>. Call the resulting matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Tr}}(M^{E})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Tr}}(M^{E})}</annotation>

</semantics>

</math><img src="./c78fb5843733819e945138b938169ea4cccf0466.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.386ex; height:3.176ex;" alt="{\displaystyle {\text{Tr}}(M^{E})}" loading="lazy">.</li>

<li>Solve <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \min _{X,Y}\min _{S\in \mathbb {R} ^{r\times r}}{\frac {1}{2}}\sum _{i,j\in E}(M_{ij}-(XSY^{\dagger })_{ij})^{2}+\rho G(X,Y)}">

</mrow>

</munder>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<mfrac>

</mfrac>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{X,Y}\min _{S\in \mathbb {R} ^{r\times r}}{\frac {1}{2}}\sum _{i,j\in E}(M_{ij}-(XSY^{\dagger })_{ij})^{2}+\rho G(X,Y)}</annotation>

</semantics>

</math><img src="./e9cb9af107bea3d0e32e4bf70f441f4309faa62a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:48.367ex; height:6.676ex;" alt="{\displaystyle \min _{X,Y}\min _{S\in \mathbb {R} ^{r\times r}}{\frac {1}{2}}\sum _{i,j\in E}(M_{ij}-(XSY^{\dagger })_{ij})^{2}+\rho G(X,Y)}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G(X,Y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G(X,Y)}</annotation>

</semantics>

</math><img src="./0af3b2570c9fb0a6a8fa462a9900691dd742f421.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.423ex; height:2.843ex;" alt="{\displaystyle G(X,Y)}" loading="lazy"> is some <a href="Regularization_(mathematics)" title="Regularization (mathematics)">regularization</a> function by <a href="Gradient_descent" title="Gradient descent">gradient descent</a> with <a href="Line_search" title="Line search">line search</a>. Initialize <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X,\;Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X,\;Y}</annotation>

</semantics>

</math><img src="./2e976a32dae99065f5946d34f78670dd655ec39d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.432ex; height:2.509ex;" alt="{\displaystyle X,\;Y}" loading="lazy"> at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{0},\;Y_{0}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{0},\;Y_{0}}</annotation>

</semantics>

</math><img src="./f0f54a0cd3c33da1d7344439363fc182cc40a04a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.062ex; height:2.509ex;" alt="{\displaystyle X_{0},\;Y_{0}}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Tr}}(M_{E})=X_{0}S_{0}Y_{0}^{\dagger }}">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Tr}}(M_{E})=X_{0}S_{0}Y_{0}^{\dagger }}</annotation>

</semantics>

</math><img src="./3652c9b356a3b5468a84822394c984ec2a8e6ff4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:19.559ex; height:3.509ex;" alt="{\displaystyle {\text{Tr}}(M_{E})=X_{0}S_{0}Y_{0}^{\dagger }}" loading="lazy">. Set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G(X,Y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G(X,Y)}</annotation>

</semantics>

</math><img src="./0af3b2570c9fb0a6a8fa462a9900691dd742f421.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.423ex; height:2.843ex;" alt="{\displaystyle G(X,Y)}" loading="lazy"> as some function forcing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X,\;Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X,\;Y}</annotation>

</semantics>

</math><img src="./2e976a32dae99065f5946d34f78670dd655ec39d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.432ex; height:2.509ex;" alt="{\displaystyle X,\;Y}" loading="lazy"> to remain incoherent throughout gradient descent if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{0}}</annotation>

</semantics>

</math><img src="./6381fdad2b9f11954b1fc2db08bbaccf634ededa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.979ex; height:2.509ex;" alt="{\displaystyle X_{0}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y_{0}}</annotation>

</semantics>

</math><img src="./d4305e31e20568c004e0e4c8540bbfe2730a42cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.405ex; height:2.509ex;" alt="{\displaystyle Y_{0}}" loading="lazy"> are incoherent.</li>

<li>Return the matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle XSY^{\dagger }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle XSY^{\dagger }}</annotation>

</semantics>

</math><img src="./fcf5596bdff547980dd3ad1634827ae96f43bcb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.342ex; height:2.676ex;" alt="{\displaystyle XSY^{\dagger }}" loading="lazy">.</li></ol>

Steps 1 and 2 of the algorithm yield a matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Tr}}(M^{E})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Tr}}(M^{E})}</annotation>

</semantics>

</math><img src="./c78fb5843733819e945138b938169ea4cccf0466.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.386ex; height:3.176ex;" alt="{\displaystyle {\text{Tr}}(M^{E})}" loading="lazy"> very close to the true matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> (as measured by the <a href="Root_mean_square_deviation" title="Root mean square deviation">root mean square error (RMSE)</a>) with high probability. In particular, with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-{\frac {1}{n^{3}}}}">

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-{\frac {1}{n^{3}}}}</annotation>

</semantics>

</math><img src="./e6d04e47eafb04b01a6e0634ac5743cb6ed348a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:7.288ex; height:5.509ex;" alt="{\displaystyle 1-{\frac {1}{n^{3}}}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{mnM_{\text{max}}^{2}}}\|M-{\text{Tr}}(M^{E})\|_{F}^{2}\leq C{\frac {r}{m|E|}}{\sqrt {\frac {m}{n}}}}">

<mfrac>

<mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mfrac>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

<mfrac>

<mrow>

</mrow>

</mrow>

</mfrac>

</mrow>

<msqrt>

<mfrac>

</mfrac>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{mnM_{\text{max}}^{2}}}\|M-{\text{Tr}}(M^{E})\|_{F}^{2}\leq C{\frac {r}{m|E|}}{\sqrt {\frac {m}{n}}}}</annotation>

</semantics>

</math><img src="./ea35acbe559069a721ff9150e6e8a223b9d7632c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:43.284ex; height:6.343ex;" alt="{\displaystyle {\frac {1}{mnM_{\text{max}}^{2}}}\|M-{\text{Tr}}(M^{E})\|_{F}^{2}\leq C{\frac {r}{m|E|}}{\sqrt {\frac {m}{n}}}}" loading="lazy"> for some constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|\cdot \|_{F}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|\cdot \|_{F}}</annotation>

</semantics>

</math><img src="./9e30c290fa57ceb0593f5dc01a5585ea1b8b54a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.467ex; height:2.843ex;" alt="{\displaystyle \|\cdot \|_{F}}" loading="lazy"> denotes the Frobenius <a href="Matrix_norm" title="Matrix norm">norm</a>. Note that the full suite of assumptions is not needed for this result to hold. The incoherence condition, for example, only comes into play in exact reconstruction. Finally, although trimming may seem counter intuitive as it involves throwing out information, it ensures projecting <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M^{E}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M^{E}}</annotation>

</semantics>

</math><img src="./96b567d2470154580c0d340c1d7dfe4847a425a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.987ex; height:2.676ex;" alt="{\displaystyle M^{E}}" loading="lazy"> onto its first <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> <a href="Principal_component_analysis" title="Principal component analysis">principal components</a> gives more information about the underlying matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> than about the observed entries.

In Step 3, the space of candidate matrices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X,\;Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X,\;Y}</annotation>

</semantics>

</math><img src="./2e976a32dae99065f5946d34f78670dd655ec39d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.432ex; height:2.509ex;" alt="{\displaystyle X,\;Y}" loading="lazy"> can be reduced by noticing that the inner minimization problem has the same solution for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (X,Y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (X,Y)}</annotation>

</semantics>

</math><img src="./41f29b9537685f499713112d6802e811cbf51bba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.597ex; height:2.843ex;" alt="{\displaystyle (X,Y)}" loading="lazy"> as for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (XQ,YR)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (XQ,YR)}</annotation>

</semantics>

</math><img src="./7b9a20f95c6362e483a96044a5555bafaaba28dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.199ex; height:2.843ex;" alt="{\displaystyle (XQ,YR)}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q}</annotation>

</semantics>

</math><img src="./8752c7023b4b3286800fe3238271bbca681219ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"> are <a href="Orthonormality" title="Orthonormality">orthonormal</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> matrices. Then <a href="Gradient_descent" title="Gradient descent">gradient descent</a> can be performed over the <a href="Cross_product" title="Cross product">cross product</a> of two <a href="Grassmannian" title="Grassmannian">Grassman manifolds</a>. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\ll m,\;n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\ll m,\;n}</annotation>

</semantics>

</math><img src="./14a24160b7e02f2d5bd8e0d0d897a425807194e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.777ex; height:2.176ex;" alt="{\displaystyle r\ll m,\;n}" loading="lazy"> and the observed entry set is in the order of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle nr\log n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle nr\log n}</annotation>

</semantics>

</math><img src="./50bb5d0e2c4e47f45a0e62183ed4841f300c95fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.584ex; height:2.509ex;" alt="{\displaystyle nr\log n}" loading="lazy">, the matrix returned by Step 3 is exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">. Then the algorithm is order optimal, since we know that for the matrix completion problem to not be <a href="Underdetermined_system" title="Underdetermined system">underdetermined</a> the number of entries must be in the order of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle nr\log n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle nr\log n}</annotation>

</semantics>

</math><img src="./50bb5d0e2c4e47f45a0e62183ed4841f300c95fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.584ex; height:2.509ex;" alt="{\displaystyle nr\log n}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Alternating_least_squares_minimization">Alternating least squares minimization</h3></div>

Alternating minimization represents a widely applicable and empirically successful approach for finding low-rank matrices that best fit the given data. For example, for the problem of low-rank matrix completion, this method is believed to be one of the most accurate and efficient, and formed a major component of the winning entry in the Netflix problem. In the alternating minimization approach, the low-rank target matrix is written in a <a href="Bilinear_form" title="Bilinear form">bilinear form</a>:

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X=UV^{T}}</annotation>

</semantics>

</math><img src="./e78f01bf90f5d9c9d3065868b6dca6bc10a0d1c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.167ex; height:2.676ex;" alt="{\displaystyle X=UV^{T}}" loading="lazy">;

the algorithm then alternates between finding the best <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> and the best <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy">. While the overall problem is non-convex, each sub-problem is typically convex and can be solved efficiently. Jain, Netrapalli and Sanghavi<a href="#cite_note-jainnetrapalli-12">[12]</a> have given one of the first guarantees for performance of alternating minimization for both matrix completion and matrix sensing.

The alternating minimization algorithm can be viewed as an approximate way to solve the following non-convex problem:

<mtr>

<mtd>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{\underset {U,V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(UV^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}}</annotation>

</semantics>

</math><img src="./7bf065804f76a06f12c87190d3c9c65fbf0541d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:36.96ex; height:5.176ex;" alt="{\displaystyle {\begin{aligned}&{\underset {U,V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(UV^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}}" loading="lazy">

The AltMinComplete Algorithm proposed by Jain, Netrapalli and Sanghavi is listed here:<a href="#cite_note-jainnetrapalli-12">[12]</a>

<ol><li>Input: observed set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>

</semantics>

</math><img src="./24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy">, values <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{\Omega }(M)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{\Omega }(M)}</annotation>

</semantics>

</math><img src="./3e23c50870dfd4401cc9a2f23af2499f9380cfb0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.163ex; height:2.843ex;" alt="{\displaystyle P_{\Omega }(M)}" loading="lazy"></li>

<li>Partition <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>

</semantics>

</math><img src="./24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy"> into <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2T+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2T+1}</annotation>

</semantics>

</math><img src="./164c76197eb1dd36cbf23b78c79628af59d33f1d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.802ex; height:2.343ex;" alt="{\displaystyle 2T+1}" loading="lazy"> subsets <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega _{0},\cdots ,\Omega _{2T}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega _{0},\cdots ,\Omega _{2T}}</annotation>

</semantics>

</math><img src="./a0724df89d5c218aa8b9c863ce8b0d33dbcaff17.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.8ex; height:2.509ex;" alt="{\displaystyle \Omega _{0},\cdots ,\Omega _{2T}}" loading="lazy"> with each element of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>

</semantics>

</math><img src="./24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy"> belonging to one of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega _{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega _{t}}</annotation>

</semantics>

</math><img src="./635203506e879a91aadea447cbca82bd3c265364.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.504ex; height:2.509ex;" alt="{\displaystyle \Omega _{t}}" loading="lazy"> with equal probability (sampling with replacement)</li>

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

<mfrac>

</mfrac>

</mrow>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {U}}^{0}=SVD({\frac {1}{p}}P_{\Omega _{0}}(M),k)}</annotation>

</semantics>

</math><img src="./e2fd46bc1eea1001935c7b7afc625f6cfd18b3d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:25.2ex; height:5.676ex;" alt="{\displaystyle {\hat {U}}^{0}=SVD({\frac {1}{p}}P_{\Omega _{0}}(M),k)}" loading="lazy"> i.e., top-<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> left singular vectors of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{p}}P_{\Omega _{0}}(M)}">

<mfrac>

</mfrac>

</mrow>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{p}}P_{\Omega _{0}}(M)}</annotation>

</semantics>

</math><img src="./4bf1d035f332c33ae039f44c981c6be6b6bb210c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:10ex; height:5.676ex;" alt="{\displaystyle {\frac {1}{p}}P_{\Omega _{0}}(M)}" loading="lazy"></li>

<li>Clipping: Set all elements of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {U}}^{0}}">

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {U}}^{0}}</annotation>

</semantics>

</math><img src="./d3b4880a08872bfe229f8b410b6f8e1b9d7a40c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.837ex; height:3.343ex;" alt="{\displaystyle {\hat {U}}^{0}}" loading="lazy"> that have magnitude greater than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {2\mu {\sqrt {k}}}{\sqrt {n}}}}">

<mfrac>

<mrow>

<msqrt>

</msqrt>

</mrow>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {2\mu {\sqrt {k}}}{\sqrt {n}}}}</annotation>

</semantics>

</math><img src="./0a47275260d7e045891e2598c7ab96b4994a9c8a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:6.547ex; height:6.843ex;" alt="{\displaystyle {\frac {2\mu {\sqrt {k}}}{\sqrt {n}}}}" loading="lazy"> to zero and orthonormalize the columns of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {U}}^{0}}">

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {U}}^{0}}</annotation>

</semantics>

</math><img src="./d3b4880a08872bfe229f8b410b6f8e1b9d7a40c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.837ex; height:3.343ex;" alt="{\displaystyle {\hat {U}}^{0}}" loading="lazy"></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=0,\cdots ,T-1}</annotation>

</semantics>

</math><img src="./c4476712e89cc46dc7c6dd774bd465fe4cf52d19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.918ex; height:2.509ex;" alt="{\displaystyle t=0,\cdots ,T-1}" loading="lazy"> do</li>

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

<msub>

<mtext>argmin</mtext>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<mover>

</mover>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \quad {\hat {V}}^{t+1}\leftarrow {\text{argmin}}_{V\in \mathbb {R} ^{n\times k}}\|P_{\Omega _{t+1}}({\hat {U}}V^{T}-M)\|_{F}^{2}}</annotation>

</semantics>

</math><img src="./dd5bd4728ff8c00f305665778f06f1ee22a52f26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:45.471ex; height:4.009ex;" alt="{\displaystyle \quad {\hat {V}}^{t+1}\leftarrow {\text{argmin}}_{V\in \mathbb {R} ^{n\times k}}\|P_{\Omega _{t+1}}({\hat {U}}V^{T}-M)\|_{F}^{2}}" loading="lazy"></li>

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

<msub>

<mtext>argmin</mtext>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \quad {\hat {U}}^{t+1}\leftarrow {\text{argmin}}_{U\in \mathbb {R} ^{m\times k}}\|P_{\Omega _{T+t+1}}(U({\hat {V}}^{t+1})^{T}-M)\|_{F}^{2}}</annotation>

</semantics>

</math><img src="./b02b37a9639ff77a545a1ee4354316d67f6534f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:52.417ex; height:4.009ex;" alt="{\displaystyle \quad {\hat {U}}^{t+1}\leftarrow {\text{argmin}}_{U\in \mathbb {R} ^{m\times k}}\|P_{\Omega _{T+t+1}}(U({\hat {V}}^{t+1})^{T}-M)\|_{F}^{2}}" loading="lazy"></li>

<li>Return <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X={\hat {U}}^{T}({\hat {V}}^{T})^{T}}">

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

<msup>

<mover>

</mover>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X={\hat {U}}^{T}({\hat {V}}^{T})^{T}}</annotation>

</semantics>

</math><img src="./283f8c20fe9f2126312ecd6a05f855f3ba646078.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.625ex; height:3.843ex;" alt="{\displaystyle X={\hat {U}}^{T}({\hat {V}}^{T})^{T}}" loading="lazy"></li></ol>

They showed that by observing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\Omega |=O(({\frac {\sigma _{1}^{*}}{\sigma _{k}^{*}}})^{6}k^{7}\log n\log(k\|M\|_{F}/\epsilon ))}">

</mrow>

</mrow>

<mfrac>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\Omega |=O(({\frac {\sigma _{1}^{*}}{\sigma _{k}^{*}}})^{6}k^{7}\log n\log(k\|M\|_{F}/\epsilon ))}</annotation>

</semantics>

</math><img src="./47de2f5d1cd7fd0f40566c311e04d06150292c45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:37.891ex; height:6.343ex;" alt="{\displaystyle |\Omega |=O(({\frac {\sigma _{1}^{*}}{\sigma _{k}^{*}}})^{6}k^{7}\log n\log(k\|M\|_{F}/\epsilon ))}" loading="lazy"> random entries of an incoherent matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">, AltMinComplete algorithm can recover <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log(1/\epsilon ))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log(1/\epsilon ))}</annotation>

</semantics>

</math><img src="./b983ffb45bd0a295d8d37dec1204be66f37dfcdc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.633ex; height:2.843ex;" alt="{\displaystyle O(\log(1/\epsilon ))}" loading="lazy"> steps. In terms of sample complexity (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\Omega |}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\Omega |}</annotation>

</semantics>

</math><img src="./cf302f4cae601b102bf8859f0a94530b0b077e37.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.972ex; height:2.843ex;" alt="{\displaystyle |\Omega |}" loading="lazy">), theoretically, Alternating Minimization may require a bigger <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>

</semantics>

</math><img src="./24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy"> than Convex Relaxation. However empirically it seems not the case which implies that the sample complexity bounds can be further tightened. In terms of time complexity, they showed that AltMinComplete needs time

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|\Omega |k^{2}\log(1/\epsilon ))}</annotation>

</semantics>

</math><img src="./2148629ec037f74a5ee766061c9778f1e2ae3835.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.257ex; height:3.176ex;" alt="{\displaystyle O(|\Omega |k^{2}\log(1/\epsilon ))}" loading="lazy">.

It is worth noting that, although convex relaxation based methods have rigorous analysis, alternating minimization based algorithms are more successful in practice.

<div class="mw-heading mw-heading3"><h3 id="Gauss-Newton">Gauss-Newton</h3></div>

A simple addition to factorization-based algorithms is Gauss–Newton Matrix Recovery (GNMR).<a href="#cite_note-Zilber2022-13">[13]</a> Similar to alternating minimization, GNMR addresses the factorized low-rank matrix completion objective:

<mtr>

<mtd>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{\underset {U,V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(UV^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}}</annotation>

</semantics>

</math><img src="./7bf065804f76a06f12c87190d3c9c65fbf0541d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:36.96ex; height:5.176ex;" alt="{\displaystyle {\begin{aligned}&{\underset {U,V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(UV^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}}" loading="lazy">

Inspired by the classical <a href="Gauss-Newton" class="mw-redirect" title="Gauss-Newton">Gauss-Newton</a> approach, GNMR linearizes the objective. This results in the following linear <a href="Least-squares" class="mw-redirect" title="Least-squares">least-squares</a> subproblem:

<mtr>

<mtd>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{\underset {\Delta U,\Delta V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(U_{0}V_{0}^{T}+U_{0}\Delta V^{T}+\Delta UV_{0}^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}}</annotation>

</semantics>

</math><img src="./f208f3f621fc9024b8990b3722184f9cf523b237.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:61.146ex; height:5.176ex;" alt="{\displaystyle {\begin{aligned}&{\underset {\Delta U,\Delta V\in \mathbb {R} ^{n\times k}}{\text{min}}}&\|P_{\Omega }(U_{0}V_{0}^{T}+U_{0}\Delta V^{T}+\Delta UV_{0}^{T})-P_{\Omega }(M)\|_{F}^{2}\\\end{aligned}}}" loading="lazy">

Starting from an initialization <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (U_{0},V_{0})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (U_{0},V_{0})}</annotation>

</semantics>

</math><img src="./08639f4f0b8cdbc54a4e00799c09f39038e7c23c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.894ex; height:2.843ex;" alt="{\displaystyle (U_{0},V_{0})}" loading="lazy">, GNMR iteratively solves the linear least squares subproblem and updates <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{t+1}\leftarrow U_{t}+\Delta U,}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{t+1}\leftarrow U_{t}+\Delta U,}</annotation>

</semantics>

</math><img src="./f5f5fa72c6de81699ba5483f5cc42e0fca8c02b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.747ex; height:2.509ex;" alt="{\displaystyle U_{t+1}\leftarrow U_{t}+\Delta U,}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{t+1}\leftarrow V_{t}+\Delta V}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V_{t+1}\leftarrow V_{t}+\Delta V}</annotation>

</semantics>

</math><img src="./9e1d1b71c45ff2cf4be4e8ba991c96a742ec91d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.64ex; height:2.509ex;" alt="{\displaystyle V_{t+1}\leftarrow V_{t}+\Delta V}" loading="lazy"> until convergence.

Since the least squares subproblem is rank deficient, GNMR selects the minimal norm solution, thereby preserving balance between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U}</annotation>

</semantics>

</math><img src="./458a728f53b9a0274f059cd695e067c430956025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.783ex; height:2.176ex;" alt="{\displaystyle U}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> without explicit regularization.

This algorithm was shown to enjoy strong theoretical guarantees. In addition, despite its simplicity, empirical results indicate that GNMR outperforms several popular algorithms, particularly when observations are sparse or the matrix is ill-conditioned.

<div class="mw-heading mw-heading3"><h3 id="Discrete-aware_matrix_completion">Discrete-aware matrix completion</h3></div>

In applications such as recommender systems, where matrix entries are discrete (e.g., integer ratings from 1 to 5), incorporating this discreteness into the matrix completion problem can improve performance. Discrete-aware matrix completion approaches introduce a regularizer that encourages the completed matrix entries to align with a finite discrete alphabet.

An early method in this domain utilized the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy">-norm as a convex relaxation of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{0}}</annotation>

</semantics>

</math><img src="./d18f7cb79dd41b63d6aca9ec6b957c225a0aea81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{0}}" loading="lazy">-norm to enforce discreteness, enabling efficient optimization using proximal gradient methods. Building upon this, Führling et al. (2023)<a href="#cite_note-Fuhrling2023-14">[14]</a> replaces the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy">-norm with a continuous and differentiable approximation of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{0}}</annotation>

</semantics>

</math><img src="./d18f7cb79dd41b63d6aca9ec6b957c225a0aea81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{0}}" loading="lazy">-norm, making the problem more tractable and improving the performance.

The discrete-aware matrix completion problem can be formulated as:

<mrow>

</mrow>

<mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\underset {{\boldsymbol {X}}\in \mathbb {R} ^{m\times n}}{\arg \min }}\,f({\boldsymbol {X}})+\lambda g({\boldsymbol {X}})+\zeta r({\boldsymbol {X}}\mid 0),}</annotation>

</semantics>

</math><img src="./58f9e1bc42d28c5ca30b6582a1001631c764aa8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:35.278ex; height:4.676ex;" alt="{\displaystyle {\underset {{\boldsymbol {X}}\in \mathbb {R} ^{m\times n}}{\arg \min }}\,f({\boldsymbol {X}})+\lambda g({\boldsymbol {X}})+\zeta r({\boldsymbol {X}}\mid 0),}" loading="lazy"></dd></dl>

where:

</mrow>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ({\boldsymbol {X}})={\frac {1}{2}}\left\|P_{\Omega }({\boldsymbol {X}}-{\boldsymbol {O}})\right\|_{F}^{2}}</annotation>

</semantics>

</math><img src="./7b7904572aeb19d2e9d0399f6ca10fcd40bd2267.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:24.63ex; height:5.176ex;" alt="{\displaystyle ({\boldsymbol {X}})={\frac {1}{2}}\left\|P_{\Omega }({\boldsymbol {X}}-{\boldsymbol {O}})\right\|_{F}^{2}}" loading="lazy"> ensures fidelity to the observed entries, with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{\Omega }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{\Omega }}</annotation>

</semantics>

</math><img src="./11d7a2019405e3cde1e00a15a5e244f490d7bef2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.911ex; height:2.509ex;" alt="{\displaystyle P_{\Omega }}" loading="lazy"> as the projection onto the observed set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>

</semantics>

</math><img src="./24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {O}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {O}}}</annotation>

</semantics>

</math><img src="./c015b3d0960fdfba7cdbac956664ff0189f9ba53.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.945ex; height:2.176ex;" alt="{\displaystyle {\boldsymbol {O}}}" loading="lazy"> as the observed matrix.</li>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g({\boldsymbol {X}})=\|{\boldsymbol {X}}\|_{*}}</annotation>

</semantics>

</math><img src="./095bdd206cba2ea5d169d2a9c20ecab2dd7fa139.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.832ex; height:2.843ex;" alt="{\displaystyle g({\boldsymbol {X}})=\|{\boldsymbol {X}}\|_{*}}" loading="lazy"> is the nuclear norm to enforce low-rank structure.</li>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

<mrow>

<mrow>

<msub>

<mover>

</mover>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r({\boldsymbol {X}}\mid 0)=\sum _{k=1}^{|{\mathcal {A}}|}\left\|\operatorname {vec} _{\overline {\Omega }}({\boldsymbol {X}})-a_{k}\mathbf {1} \right\|_{0}}</annotation>

</semantics>

</math><img src="./2f3607c122738a443956f1b81cbff841cbb4aa98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:33.716ex; height:7.676ex;" alt="{\displaystyle r({\boldsymbol {X}}\mid 0)=\sum _{k=1}^{|{\mathcal {A}}|}\left\|\operatorname {vec} _{\overline {\Omega }}({\boldsymbol {X}})-a_{k}\mathbf {1} \right\|_{0}}" loading="lazy"> is the discrete-space regularizer, with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {A}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {A}}}</annotation>

</semantics>

</math><img src="./280ae03440942ab348c2ca9b8db6b56ffa9618f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.903ex; height:2.343ex;" alt="{\displaystyle {\mathcal {A}}}" loading="lazy"> being the discrete alphabet (e.g., {1, 2, 3, 4, 5}) and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\overline {\Omega }}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\overline {\Omega }}}</annotation>

</semantics>

</math><img src="./86f6b4b87fefc0caa4b0619fb9aa46d617a12359.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.793ex; height:3.009ex;" alt="{\displaystyle {\overline {\Omega }}}" loading="lazy"> the set of unobserved entries.</li></ul>

To solve this non-convex problem, the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{0}}</annotation>

</semantics>

</math><img src="./d18f7cb79dd41b63d6aca9ec6b957c225a0aea81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{0}}" loading="lazy">-norm is approximated by a continuous function. This approximation is convexized using fractional programming, transforming the problem into a series of convex subproblems.

The algorithm iteratively updates the matrix estimate by applying proximal operations to the discrete-space regularizer and singular value thresholding to enforce the low-rank constraint. Initializing the process with the solution from the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy">-norm-based method can accelerate convergence. Simulation results, tested on datasets like MovieLens-100k, demonstrate that this method outperforms both its <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy">-norm-based predecessor and other state-of-the-art techniques, particularly when the ratio of observed entries is low (e.g., 20% to 60%).<a href="#cite_note-Fuhrling2023-14">[14]</a>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

Several applications of matrix completion are summarized by Candès and Plan<a href="#cite_note-candesplan-9">[9]</a> as follows:

<div class="mw-heading mw-heading3"><h3 id="Collaborative_filtering">Collaborative filtering</h3></div>

<a href="Collaborative_filtering" title="Collaborative filtering">Collaborative filtering</a> is the task of making automatic predictions about the interests of a user by collecting taste information from many users. Companies like Apple, Amazon, Barnes and Noble, and Netflix are trying to predict their user preferences from partial knowledge. In these kind of matrix completion problem, the unknown full matrix is often considered low rank because only a few factors typically contribute to an individual's tastes or preference.

<div class="mw-heading mw-heading3"><h3 id="System_identification">System identification</h3></div>

In control, one would like to fit a discrete-time linear time-invariant state-space model

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}x(t+1)&=Ax(t)+Bu(t)\\y(t)&=Cx(t)+Du(t)\end{aligned}}}</annotation>

</semantics>

</math><img src="./990179437fd89ac196e907351a7a273ad3e4c165.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:26.32ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}x(t+1)&=Ax(t)+Bu(t)\\y(t)&=Cx(t)+Du(t)\end{aligned}}}" loading="lazy"></dd></dl>

to a sequence of inputs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u(t)\in \mathbb {R} ^{m}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u(t)\in \mathbb {R} ^{m}}</annotation>

</semantics>

</math><img src="./5a1831782d6f41d9f785d3827b09d9cacee97337.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.172ex; height:2.843ex;" alt="{\displaystyle u(t)\in \mathbb {R} ^{m}}" loading="lazy"> and outputs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y(t)\in \mathbb {R} ^{p},t=0,\ldots ,N}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y(t)\in \mathbb {R} ^{p},t=0,\ldots ,N}</annotation>

</semantics>

</math><img src="./84b2f761d7b248686f4f29abb9d6b30c31223474.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.759ex; height:2.843ex;" alt="{\displaystyle y(t)\in \mathbb {R} ^{p},t=0,\ldots ,N}" loading="lazy">. The vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x(t)\in \mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(t)\in \mathbb {R} ^{n}}</annotation>

</semantics>

</math><img src="./2c1c961584277244025a31559591d69d7f925ef0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.716ex; height:2.843ex;" alt="{\displaystyle x(t)\in \mathbb {R} ^{n}}" loading="lazy"> is the state of the system at time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is the order of the system model. From the input/output pair, one would like to recover the matrices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A,B,C,D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A,B,C,D}</annotation>

</semantics>

</math><img src="./684d01c09b12e5a28987c6127567daef29ee3b44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.3ex; height:2.509ex;" alt="{\displaystyle A,B,C,D}" loading="lazy"> and the initial state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x(0)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x(0)}</annotation>

</semantics>

</math><img src="./8f7176643e6d36fa7674dc79fdff1a4daa068f5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.301ex; height:2.843ex;" alt="{\displaystyle x(0)}" loading="lazy">. This problem can also be viewed as a low-rank matrix completion problem.

<div class="mw-heading mw-heading3"><h3 id="Internet_of_things_(IoT)_localization">Internet of things (IoT) localization</h3></div>

The localization (or global positioning) problem emerges naturally in IoT sensor networks. The problem is to recover the sensor map in <a href="Euclidean_space" title="Euclidean space">Euclidean space</a> from a local or partial set of pairwise distances. Thus it is a matrix completion problem with rank two if the sensors are located in a 2-D plane and three if they are in a 3-D space.<a href="#cite_note-nguyenkimkimshim-18">[18]</a>

<div class="mw-heading mw-heading3"><h3 id="Social_networks_recovery">Social networks recovery</h3></div>

Most of the real-world social networks have low-rank distance matrices. When we are not able to measure the complete network, which can be due to reasons such as private nodes, limited storage or compute resources, we only have a fraction of distance entries known. Criminal networks are a good example of such networks. Low-rank Matrix Completion can be used to recover these unobserved distances.<a href="#cite_note-topologyrecovery-19">[19]</a>

/* start https://en.wikipedia.org/ */

.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}

/* end https://en.wikipedia.org/ */

</style><div class="div-col" style="column-width: 25em;">

<ul><li><a href="Matrix_regularization" title="Matrix regularization">Matrix regularization</a></li>

<li><a href="Netflix_Prize" title="Netflix Prize">Netflix Prize</a></li>

<li><a href="Collaborative_filtering" title="Collaborative filtering">Collaborative filtering</a></li>

<li><a href="System_identification" title="System identification">System identification</a></li>

<li><a href="Convex_optimization" title="Convex optimization">Convex optimization</a></li>

<li><a href="Imputation_(statistics)" title="Imputation (statistics)">Imputation</a></li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFJohnson1990" class="citation book cs1">Johnson, Charles R. (1990). "Matrix completion problems: A survey". Matrix Theory and Applications. Proceedings of Symposia in Applied Mathematics. Vol. 40. pp. 171–198. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fpsapm%2F040%2F1059486">10.1090/psapm/040/1059486</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780821801543</bdi>.</cite>

</li>

<cite id="CITEREFLaurent2008" class="citation book cs1">Laurent, Monique (2008). "Matrix Completion Problems". Encyclopedia of Optimization. Vol. 3. pp. 221–229. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-0-387-74759-0_355">10.1007/978-0-387-74759-0_355</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-74758-3</bdi>.</cite>

</li>

<cite id="CITEREFCandèsRecht2009" class="citation journal cs1">Candès, E. J.; Recht, B. (2009). <a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10208-009-9045-5">"Exact Matrix Completion via Convex Optimization"</a>. <a href="Foundations_of_Computational_Mathematics" title="Foundations of Computational Mathematics">Foundations of Computational Mathematics</a>. 9 (6): 717–772. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0805.4471">0805.4471</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10208-009-9045-5">10.1007/s10208-009-9045-5</a>.</cite>

</li>

<cite id="CITEREFRecht2009" class="citation journal cs1">Recht, B. (2009). <a rel="nofollow" class="external text" href="http://www.jmlr.org/papers/volume12/recht11a/recht11a.pdf">"A Simpler Approach to Matrix Completion"</a> (PDF). <a href="Journal_of_Machine_Learning_Research" title="Journal of Machine Learning Research">Journal of Machine Learning Research</a>. 12: 3413–3430. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0910.0651">0910.0651</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2009arXiv0910.0651R">2009arXiv0910.0651R</a>.</cite>

</li>

<cite id="CITEREFXu2018" class="citation journal cs1">Xu, Zhiqiang (2018). "The minimal measurement number for low-rank matrix recovery". <a href="Applied_and_Computational_Harmonic_Analysis" title="Applied and Computational Harmonic Analysis">Applied and Computational Harmonic Analysis</a>. 44 (2): 497–508. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1505.07204">1505.07204</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.acha.2017.01.005">10.1016/j.acha.2017.01.005</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11990443">11990443</a>.</cite>

</li>

<cite id="CITEREFCandèsTao2010" class="citation journal cs1">Candès, E. J.; Tao, T. (2010). "The Power of Convex Relaxation: Near-Optimal Matrix Completion". <a href="IEEE_Transactions_on_Information_Theory" title="IEEE Transactions on Information Theory">IEEE Transactions on Information Theory</a>. 56 (5): 2053–2080. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0903.1476">0903.1476</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.2010.2044061">10.1109/TIT.2010.2044061</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1255437">1255437</a>.</cite>

</li>

<cite id="CITEREFTao2009" class="citation web cs1">Tao, T. (10 March 2009). <a rel="nofollow" class="external text" href="http://terrytao.wordpress.com/2009/03/10/the-power-of-convex-relaxation-near-optimal-matrix-completion/">"The power of convex relaxation: near-optimal matrix completion"</a>. What's new.</cite>

</li>

<cite id="CITEREFNguyenKimShim2019" class="citation journal cs1">Nguyen, L.T.; Kim, J.; Shim, B. (10 July 2019). "Low-Rank Matrix Completion: A Contemporary Survey". <a href="IEEE_Access" title="IEEE Access">IEEE Access</a>. 7 (1): 94215–94237. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1907.11705">1907.11705</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2019arXiv190711705N">2019arXiv190711705N</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FACCESS.2019.2928130">10.1109/ACCESS.2019.2928130</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:198930899">198930899</a>.</cite>

</li>

<cite id="CITEREFCandèsPlan2010" class="citation journal cs1">Candès, E. J.; Plan, Y. (2010). "Matrix Completion with Noise". <a href="Proceedings_of_the_IEEE" title="Proceedings of the IEEE">Proceedings of the IEEE</a>. 98 (6): 925–936. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0903.3131">0903.3131</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FJPROC.2009.2035722">10.1109/JPROC.2009.2035722</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:109721">109721</a>.</cite>

</li>

<cite id="CITEREFErikssonBalzanoNowak2011" class="citation arxiv cs1">Eriksson, B.; Balzano, L.; Nowak, R. (2011). "High-Rank Matrix Completion and Subspace Clustering with Missing Data". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1112.5629">1112.5629</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.IT">cs.IT</a>].</cite>

</li>

<cite id="CITEREFKeshavanMontanariOh2010" class="citation journal cs1">Keshavan, R. H.; Montanari, A.; Oh, S. (2010). "Matrix Completion from a Few Entries". <a href="IEEE_Transactions_on_Information_Theory" title="IEEE Transactions on Information Theory">IEEE Transactions on Information Theory</a>. 56 (6): 2980–2998. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0901.3150">0901.3150</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.2010.2046205">10.1109/TIT.2010.2046205</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:53504">53504</a>.</cite>

</li>

<cite id="CITEREFJainNetrapalliSanghavi2013" class="citation book cs1">Jain, P.; Netrapalli, P.; Sanghavi, S. (2013). "Low-rank Matrix Completion using Alternating Minimization". Proceedings of the 45th annual ACM symposium on Symposium on theory of computing. ACM. pp. 665–674. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1212.0467">1212.0467</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2488608.2488693">10.1145/2488608.2488693</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-2029-0</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:447011">447011</a>.</cite>

</li>

<li id="cite_note-Zilber2022-13">^ <a href="#cite_ref-Zilber2022_13-0">a</a> <a href="#cite_ref-Zilber2022_13-1">b</a> <cite id="CITEREFZilber,_PiniNadler,_Boaz2022" class="citation journal cs1">Zilber, Pini; Nadler, Boaz (2022). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC11784930">"GNMR: A provable one-line algorithm for low rank matrix recovery"</a>. SIAM Journal on Mathematics of Data Science. 4 (2): 909–934. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F21M1433812">10.1137/21M1433812</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC11784930">11784930</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/39896132">39896132</a>.</cite>

</li>

<li id="cite_note-Fuhrling2023-14">^ <a href="#cite_ref-Fuhrling2023_14-0">a</a> <a href="#cite_ref-Fuhrling2023_14-1">b</a> <a href="#cite_ref-Fuhrling2023_14-2">c</a> <cite id="CITEREFFührling,_NiclasAndo,_KengoAbreu,_Giuseppe_Thadeu_Freitas_deGonzález_G.,_David2023" class="citation journal cs1">Führling, Niclas; Ando, Kengo; Abreu, Giuseppe Thadeu Freitas de; González G., David; Gonsa, Osvaldo (2023). "Discrete Aware Matrix Completion via Convexized \ell_0-Norm Approximation". IEEE Transactions on Signal Processing. XX (X): XXX–XXX. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTSP.2023.XXXXXXX">10.1109/TSP.2023.XXXXXXX</a> (inactive 1 July 2025).</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: DOI inactive as of July 2025 (link)

</li>

<cite id="CITEREFCaiCandèsShen2010" class="citation journal cs1">Cai, J.-F.; Candès, E. J.; Shen, Z. (2010). "A Singular Value Thresholding Algorithm for Matrix Completion". <a href="SIAM_Journal_on_Optimization" class="mw-redirect" title="SIAM Journal on Optimization">SIAM Journal on Optimization</a>. 20 (4): 1956–1982. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0810.3286">0810.3286</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F080738970">10.1137/080738970</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1254778">1254778</a>.</cite>

</li>

<cite id="CITEREFBertsimasCory-WrightPauphilet2021" class="citation journal cs1">Bertsimas, Dimitris; Cory-Wright, Ryan; Pauphilet, Jean (2021). "Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints". <a href="Operations_Research" class="mw-redirect" title="Operations Research">Operations Research</a>. 70 (6): 3321–3344. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2009.10395">2009.10395</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fopre.2021.2182">10.1287/opre.2021.2182</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:221836263">221836263</a>.</cite>

</li>

<cite id="CITEREFBertsimasCory-WrightPauphilet2023" class="citation journal cs1">Bertsimas, Dimitris; Cory-Wright, Ryan; Pauphilet, Jean (2023). "A New Perspective on Low-Rank Optimization". Optimization Online. 202 (1–2): 47–92. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2105.05947">2105.05947</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10107-023-01933-9">10.1007/s10107-023-01933-9</a>.</cite>

</li>

<cite id="CITEREFNguyenKimKimShim2019" class="citation journal cs1">Nguyen, L.T.; Kim, J.; Kim, S.; Shim, B. (2019). "Localization of IoT Networks Via Low-Rank Matrix Completion". <a href="IEEE_Transactions_on_Communications" title="IEEE Transactions on Communications">IEEE Transactions on Communications</a>. 67 (8): 5833–5847. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTCOMM.2019.2915226">10.1109/TCOMM.2019.2915226</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:164605437">164605437</a>.</cite>

</li>

<cite id="CITEREFMahindreJayasumanaGajamannagePaffenroth2019" class="citation book cs1">Mahindre, G.; Jayasumana, A.P.; Gajamannage, K.; Paffenroth, R. (2019). "On Sampling and Recovery of Topology of Directed Social Networks – A Low-Rank Matrix Completion Based Approach". 2019 IEEE 44th Conference on Local Computer Networks (LCN). IEEE. pp. 324–331. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FLCN44214.2019.8990707">10.1109/LCN44214.2019.8990707</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-7281-1028-8</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:211206354">211206354</a>.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-12" href="https://en.wikipedia.org/wiki/?title=Matrix_completion&oldid=1300099373">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>